package leetcode.primary;

import java.util.ArrayList;
import java.util.List;

public class T312 {
    List<Integer> list;
    public int maxCoins(int[] nums) {
        int length = nums.length;
        if (length==1){
            return nums[0];
        }
        list = new ArrayList<>();
        for (int num : nums) {
            list.add(num);
        }
        int maxCoins = 0;
        for (int i = 0; i < length - 2; i++) {
            int index = findMin();
            int coins;
            coins = list.get(index-1)*list.get(index)*list.get(index+1);
            System.out.println("index="+index+",coins="+coins);
            maxCoins+=coins;
            list.remove(index);
        }
        maxCoins+=list.get(0)*list.get(1)+Math.max(list.get(0),list.get(1));
        return maxCoins;

    }

    private int findMin(){
        int min = 101;
        int index = 0;
        for (int i = 1; i < list.size()-1; i++) {
            if (list.get(i)<=min){
                min = list.get(i);
                index = i;
            }
        }
        return index;
    }

    public static void main(String[] args) {
        T312 t312 = new T312();
        int maxCoins = t312.maxCoins(new int[]{9,76,64,21,97,60});
        System.out.println(maxCoins);
    }
}
